package org.usmile.algorithms.leetcode.middle;

/**
 * 487. 最大连续1的个数 II
 *
 * 给定一个二进制数组 nums ，如果最多可以翻转一个 0 ，则返回数组中连续 1 的最大个数。
 *
 * 示例 1：
 * 输入：nums = [1,0,1,1,0]
 * 输出：4
 * 解释：翻转第一个 0 可以得到最长的连续 1。
 *      当翻转以后，最大连续 1 的个数为 4。
 *
 * 示例 2:
 * 输入：nums = [1,0,1,1,0,1]
 *
 * 输出：4
 *
 * 提示:
 * 1 <= nums.length <= 105
 * nums[i] 不是 0 就是 1.
 *
 * 进阶：如果输入的数字是作为 无限流 逐个输入如何处理？换句话说，内存不能存储下所有从流中输入的数字。您可以有效地解决吗？
 */
public class _0487 {
}

class _0487_Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int max = 0;
        int left = 0;
        int right = 0;
        int zeroIndex = -1;
        while (right < nums.length) {
            if (nums[right] == 0) {
                if (zeroIndex >= 0) {
                    left = zeroIndex + 1;
                }
                zeroIndex = right;
            }
            max = Math.max(max, right - left + 1);
            right++;
        }

        return max;
    }
}

class _0487_Solution1 {
    public int findMaxConsecutiveOnes(int[] nums) {
        int left = 0;
        int right = 0;
        int max = 0;
        int windowZeros = 0;
        while (right < nums.length) {
            if (nums[right] == 0) {
                windowZeros++;
            }
            while (windowZeros > 1) {
                if (nums[left] == 0) {
                    windowZeros--;
                }

                left++;
            }
            max = Math.max(max, right - left + 1);
            right++;
        }

        return max;
    }
}